package com.shm.leetcode;

/**
 * 397. 整数替换
 * 给定一个正整数 n ，你可以做如下操作：
 *
 * 如果 n 是偶数，则用 n / 2替换 n 。
 * 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
 * n 变为 1 所需的最小替换次数是多少？
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 8
 * 输出：3
 * 解释：8 -> 4 -> 2 -> 1
 * 示例 2：
 *
 * 输入：n = 7
 * 输出：4
 * 解释：7 -> 8 -> 4 -> 2 -> 1
 * 或 7 -> 6 -> 3 -> 2 -> 1
 * 示例 3：
 *
 * 输入：n = 4
 * 输出：2
 *
 *
 * 提示：
 *
 * 1 <= n <= 231 - 1
 * @author SHM
 */
public class IntegerReplacement {
    /**
     * 方法一：枚举所有的情况
     * 思路与算法
     *
     * 我们可以使用递归的方法枚举所有将 nn 变为 11 的替换序列：
     *
     * 当 nn 为偶数时，我们只有唯一的方法将 nn 替换为 \dfrac{n}{2}
     * 2
     * n
     * ​
     *  。
     *
     * 当 nn 为奇数时，我们可以选择将 nn 增加 11 或减少 11。由于这两种方法都会将 nn 变为偶数，那么下一步一定是除以 22，因此这里我们可以看成使用两次操作，将 nn 变为 \dfrac{n+1}{2}
     * 2
     * n+1
     * ​
     *   或 \dfrac{n-1}{2}
     * 2
     * n−1
     * ​
     *  。
     *
     * 细节
     *
     * 当 n = 2^{31}-1n=2
     * 31
     *  −1 时，计算 n+1n+1 会导致溢出，因此我们可以使用整数除法 \lfloor \dfrac{n}{2} \rfloor + 1⌊
     * 2
     * n
     * ​
     *  ⌋+1 和 \lfloor \dfrac{n}{2} \rfloor⌊
     * 2
     * n
     * ​
     *  ⌋ 分别计算 \dfrac{n+1}{2}
     * 2
     * n+1
     * ​
     *   或 \dfrac{n-1}{2}
     * 2
     * n−1
     * ​
     *  ，其中 \lfloor \cdot \rfloor⌊⋅⌋ 表示向下取整。
     *  复杂度分析
     *
     * 时间复杂度：O(\phi ^{\log n})O(ϕ
     * logn
     *  )，其中 \phi = \dfrac{1+\sqrt{5}}{2} \approx 1.618ϕ=
     * 2
     * 1+
     * 5
     * ​
     *
     * ​
     *  ≈1.618 表示黄金分割比。
     *
     * 时间复杂度的准确证明较为复杂，这里给出一种直观上的叙述，感兴趣的读者可以自行展开思考：
     *
     * 在递归的过程中，递归树的同一层上最小的 nn 值和最大的 nn 值相差不会超过 11，这里可以使用数学归纳法证明。
     *
     * 如果递归树的上一层出现的值为 xx 和 x+1x+1，它们分别被递归调用了 pp 和 qq 次，而当前层出现的值为 yy 和 y+1y+1，那么它们分别会被递归调用：
     *
     * 要么 pp 和 p+qp+q 次；
     *
     * 要么 p+qp+q 和 qq 次。
     *
     * 这类似于斐波那契数列的递推式。
     *
     * 因此 l = O(\log n)l=O(logn) 层的递归树中所有 nn 值被调用的次数之和为 O(\text{fib}(l)) = O(\text{fib}(\log n))O(fib(l))=O(fib(logn))，其中 \text{fib}(\cdot)fib(⋅) 表示斐波那契数列的对应项。由于 \text{fib}(l) = O(\phi^l)fib(l)=O(ϕ
     * l
     *  )，因此算法的时间复杂度为 O(\phi ^{\log n})O(ϕ
     * logn
     *  )。
     *
     * 空间复杂度：O(\log n)O(logn)。每一次递归都会将 nn 减小一半，因此需要 O(\log n)O(logn) 的栈空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/integer-replacement/solution/zheng-shu-ti-huan-by-leetcode-solution-swef/
     * @param n
     * @return
     */
    public int integerReplacement(int n) {
        if(n==1){
            return 0;
        }
        if (n%2==0){
            return 1+integerReplacement(n/2);
        }
//        return 1+Math.min(integerReplacement(n-1),integerReplacement(n+1)); //当 n = 2^{31}-1n=2
//31
// −1 时，计算 n+1n+1 会导致溢出
//        return 2+Math.min(integerReplacement((n-1)/2),integerReplacement((n+1)/2));//当 n = 2^{31}-1n=2
//31
// −1 时，计算 n+1n+1 会导致溢出
        return 2+Math.min(integerReplacement(n/2),integerReplacement(n/2+1));
    }
}
